package solution1.demo.demo7;

import java.util.*;

public class Solution {

    //1.堆排
    public void heapSort(int[] arr) {
        //建立大根堆
        createBigHeap(arr);
        for(int i = arr.length - 1; i >= 0; i--) {
            swap(arr, 0, i);
            adjustDown(arr, 0, i);
        }
    }

    private void createBigHeap(int[] arr) {
        int len = arr.length;
        for(int parent = (len - 1 - 1) / 2; parent >= 0; parent--) {
            //对每一颗子树进行向下调整
            adjustDown(arr, parent, len);
        }
    }

    private void adjustDown(int[] arr, int parent, int len) {
        //向下调整
        int child = parent * 2 + 1;
        while(child < len) {
            if(child + 1 < len && arr[child] < arr[child + 1]) {
                child++;
            }
            if(arr[child] > arr[parent]) {
                //交换
                swap(arr, child, parent);
                //继续向下调整
                parent = child;
                child = child * 2 + 1;
            } else {
                break;
            }
        }
    }

    private void swap(int[] arr, int child, int parent) {
        int tmp = arr[child];
        arr[child] = arr[parent];
        arr[parent] = tmp;
    }

    //2.快速排序
    public void quickSort(int[] arr) {
        quick(arr, 0, arr.length - 1);
    }

    private void quick(int[] arr, int left, int right) {
        if(left >= right) {
            return;
        }
        //三数取中
        int mid = fundMid(arr, left, right);
        swap(arr, left, mid);
        //找基准
        int point = fundPoint(arr, left, right);
        quick(arr, left, point - 1);
        quick(arr, point + 1, right);
    }

    private int fundMid(int[] arr, int left, int right) {
        int mid = (left + right) / 2;
        if(arr[left] < arr[right]) {
            if(arr[left] > arr[mid]) {
                return left;
            } else if(arr[mid] > arr[right]) {
                return right;
            } else {
                return mid;
            }
        } else {
            if(arr[right] > arr[mid]) {
                return right;
            } else if(arr[mid] > arr[left]) {
                return left;
            } else {
                return mid;
            }
        }
    }

    private int fundPoint(int[] arr, int start, int end) {
        int key = arr[start];
        while(start < end) {
            while(start < end && arr[end] > key) {
                end--;
            }
            arr[start] = arr[end];
            while(start < end && arr[start] < key) {
                start++;
            }
            arr[end] = arr[start];
        }
        arr[start] = key;
        return start;
    }

    //3.两数之和
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        for(int i = 0; i < nums.length; i++) {
            if(map.containsKey(target - nums[i])) {
                int[] arr = new int[2];
                arr[0] = map.get(target - nums[i]);
                arr[1] = i;
                return arr;
            }
            map.put(nums[i], i);
        }
        return new int[0];
    }

//    //4.三数之和
//    public List<List<Integer>> threeSum(int[] nums) {
//        //排序
//        Arrays.sort(nums);
//        List<List<Integer>> res = new ArrayList<>();
//        int len = nums.length;
//        for(int i = 0; i < len; i++) {
//            if(nums[i] > 0) {
//                //排好序还大于 0 ，后面的肯定都大于0
//                break;
//            }
//            //去重
//            if(i > 0 && nums[i] == nums[i - 1]) {
//                continue;
//            }
//            //双指针
//            int left = i + 1;
//            int right = len - 1;
//            while(left < right) {
//                int sum = nums[left] + nums[right] + nums[i];
//                if(sum > 0) {
//                    //向左，顺便去重
//                    while(left < right && nums[right] == nums[--right]);
//                } else if(sum < 0) {
//                    while(left < right && nums[left] == nums[++left]);
//                } else {
//                    //找到了
//                    List<Integer> list = new ArrayList<>();
//                    list.add(nums[left]);
//                    list.add(nums[right]);
//                    list.add(nums[i]);
//                    res.add(list);
//                    //左右去重
//                    while(left < right && nums[right] == nums[--right]);
//                    while(left < right && nums[left] == nums[++left]);
//                }
//            }
//        }
//        return res;
//    }


    //5.三数之和
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> res = new ArrayList<>();
        int len = nums.length;
        for(int i = 0; i < len; i++) {
            if(nums[i] > 0) {//作为根元素
                break;
            }
            if(i >= 1 && nums[i] == nums[i - 1]) {
                continue;
            }
            int left = i + 1;
            int right = len - 1;
            while(left < right) {
                int sum = nums[i] + nums[left] + nums[right];
                if(sum < 0) {
                    while(left < right && nums[left] == nums[++left]);
                } else if(sum > 0) {
                    while(left < right && nums[right] == nums[--right]);
                } else {
                    List<Integer> list = new ArrayList<>();
                    list.add(nums[i]);
                    list.add(nums[left]);
                    list.add(nums[right]);
                    res.add(list);
                    while(left < right && nums[left] == nums[++left]);
                    while(left < right && nums[right] == nums[--right]);
                }
            }
        }
        return res;
    }

    //6.滑动窗口的最大值
    public int[] maxSlidingWindow(int[] nums, int k) {
        if(k == 1) {
            return nums;
        }
        //双端单调队列
        Deque<Integer> deque = new LinkedList<>();
        int len = nums.length;
        int[] res = new int[len - k + 1];
        int index = 0;//res 指针
        deque.offerLast(nums[0]);
        for(int i = 1; i < len; i++) {
            if(i < k - 1) {
                //维护一个单调对列
                while(!deque.isEmpty() && deque.peekLast() < nums[i]) {
                    deque.pollLast();
                }
                deque.offerLast(nums[i]);
            } else {
                //加入滑动窗口的最后一个数，以及提出滑动窗口的第一个数
                while(!deque.isEmpty() && deque.peekLast() < nums[i]) {
                    deque.pollLast();
                }
                deque.offerLast(nums[i]);
                res[index++] = deque.peekFirst();
                if(nums[i - k + 1] == deque.peekFirst()) {
                    deque.pollFirst();
                }
            }
        }
        return res;
    }

//    //7.组合(回溯)
//    private List<List<Integer>> res = new ArrayList<>();
//    private List<Integer> list = new ArrayList<>();
//    public List<List<Integer>> combine(int n, int k) {
//        fundCombine(1, n, k);
//        return res;
//    }
//
//    public void fundCombine(int begin, int n, int k) {
//        if(list.size() == k) {
//            res.add(new ArrayList<>(list));
//            return;
//        }
//        for(int i = begin; i <= n; i++) {
//            list.add(i);
//            fundCombine(i + 1, n, k);
//            list.remove(list.size() - 1);
//        }
//    }

//    //8.组合总和 III(回溯)
//    private List<List<Integer>> res = new ArrayList<>();
//    private List<Integer> list = new ArrayList<>();
//    public List<List<Integer>> combinationSum3(int k, int n) {
//        fundCombinSum(1, k, n);
//        return res;
//    }
//
//    private void fundCombinSum(int begin, int k, int n) {
//        if(n < 0) {
//            return;
//        }
//        if(n == 0 && k == 0) {
//            res.add(new ArrayList<>(list));
//            return;
//        }
//        for(int i = begin; i <= 9; i++) {
//            list.add(i);
//            fundCombinSum(i + 1, k - 1, n - i);
//            list.remove(list.size() - 1);
//        }
//    }    private List<String> list = new ArrayList<>();
//    private StringBuilder path = new StringBuilder();
//    private String[] map = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs",
//            "tuv", "wxyz"};
//    public List<String> letterCombinations(String digits) {
//        int len = digits.length;
//        if(len == 0) {
//            return list;
//        }
//        char[] nums = digits.toArrayChar();
//        letterDfs(0, nums);
//        return list;
//    }
//
//    private void letterDfs(int begin, char[] nums) {
//        if(nums.length == path.size()) {
//            list.add(path.toString());
//            return;
//        }
//        for(int i = 0; i < nums.length; i++) {
//            for(int j = begin; j < )
//        }
//
//    }


//    //9.电话号码的字母组合(回溯)
//    private List<String> list = new ArrayList<>();
//    private StringBuilder path = new StringBuilder();
//    private String[] map = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs",
//            "tuv", "wxyz"};
//    public List<String> letterCombinations(String digits) {
//        int len = digits.length();
//        if(len == 0) {
//            return list;
//        }
//        letterDfs(0, digits);
//        return list;
//    }
//
//    private void letterDfs(int begin, String digits) {
//        if (digits.length() == path.length()) {
//            list.add(path.toString());
//            return;
//        }
//        for (int i = 0; i < digits.length(); i++) {
//            //得到对应的电话号码
//            int num = digits.charAt(i) - '0';
//            for (int j = 0; j < map[num].length(); j++) {
//                path.append(map[num].charAt(j));
//                letterDfs(i + 1, digits);
//                path.deleteCharAt(path.length() - 1);
//            }
//        }
//    }

    //10.组合总数(回溯)
    private List<List<Integer>> res = new ArrayList<>();
    private List<Integer> list = new ArrayList<>();
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        fundCombinaSum(candidates, target, 0);
        return res;
    }

    private void fundCombinaSum(int[] candidates, int target, int begin) {
        if(target == 0) {
            res.add(new ArrayList<>(list));
            return;
        }
        for(int i = begin; i < candidates.length; i++) {
            if(target - candidates[i] < 0) {
                continue;
            }
            list.add(candidates[i]);
            fundCombinaSum(candidates, target - candidates[i], i);
            list.remove(list.size() - 1);
        }
    }

}

class Main {
    public static void main(String[] args) {
        int[] arr = {2,3,6,7};
        Solution solution = new Solution();
        solution.combinationSum(arr, 7);
    }
}
